package search;

public class InsertValueSearch {
    public static void main(String[] args) {
//        int[] arr = {2,2,2,2,2};
//        int ret = insertValueSearch(arr, 0, arr.length - 1, 2);  // 除零错误
        int[] arr = {2,3,4,8,9,20};
        int ret = insertValueSearch(arr, 0, arr.length - 1, 2);
        System.out.println(ret);
    }

    /**
     * 插值查找 比较适合值“分布均匀” “数据量大" 的有序序列
     * 公式：  int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
     * @param arr 待排序数组
     * @param left 最左端下标
     * @param right 最右端下标
     * @param findVal 需要查找的值
     * @return 查找值的下标
     */
    public static int insertValueSearch(int[] arr, int left, int right, int findVal) {
        System.out.println("hh");
        if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) { //防止数组下标越界，因为findVal是你给定的
            return -1;
        }
        int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
        int midVal = arr[mid];
        if (midVal > findVal) {
            return insertValueSearch(arr, left, mid - 1, findVal);
        } else if (midVal < findVal) {
            return insertValueSearch(arr, mid + 1, right, findVal);
        } else {
            return mid;
        }
    }
}
